package codeTop;

import java.util.HashMap;
import java.util.Map;

public class q76 {
    public String minWindow(String s, String t) {
        int start = 0;
        int maxLen = Integer.MAX_VALUE;
        String res = "";
        int count = t.length();
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            map.put(t.charAt(i),map.getOrDefault(t.charAt(i),0)+1);
        }
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                Integer num = map.get(s.charAt(i));
                if (num > 0) {
                    count--;
                }
                map.put(s.charAt(i),num-1);
                if (count == 0) {
                    while (start < i) {
                        if (!map.containsKey(s.charAt(start))) {
                            start++;
                        }else {
                            if (map.get(s.charAt(start)) < 0) {
                                map.put(s.charAt(start),map.get(s.charAt(start))+1);
                                start++;
                            }else {
                                break;
                            }
                        }
                    }
                    int len = i-start+1;
                    if (len < maxLen) {
                        maxLen =  len;
                        res = s.substring(start,i+1);
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        q76 q = new q76();
        System.out.println(q.minWindow("ADOBECODEBANC", "ABC"));
    }
}
